package com.lw.leetcode.back.b;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 39. 组合总和
 * 剑指 Offer II 081. 允许重复选择元素的组合
 *
 * @author liw
 * @version 1.0
 * @date 2021/9/15 10:35
 */
public class CombinationSum {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>>[] dp = new ArrayList[target + 1];
        List<List<Integer>> a = new ArrayList<>();
        List<Integer> item = new ArrayList<>();
        a.add(item);
        dp[0] = a;
        if (candidates == null || candidates.length == 0) {
            return a;
        }
        Arrays.sort(candidates);
        for (int i = 1; i <= target; i++) {
            a = new ArrayList<>();
            for (int candidate : candidates) {
                int j = i - candidate;
                if (j >= 0) {
                    List<List<Integer>> lists = dp[j];
                    for (List<Integer> list : lists) {
                        if ((list.size() > 0 && list.get(list.size() - 1) >= candidate) || list.size() == 0) {
                            item = new ArrayList<>(list.size() + 1);
                            item.addAll(list);
                            item.add(candidate);
                            a.add(item);
                        }
                    }
                }
            }
            dp[i] = a;
        }
        return dp[target];
    }

}
